#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAXSIZE 100

typedef struct
{
    char data[MAXSIZE];
    int top;
} CharStack;

typedef struct
{
    int data[MAXSIZE];
    int top;
} IntStack;

void InitCharStack(CharStack *s)
{
    s->top = -1;
}
void InitIntStack(IntStack *s)
{
    s->top = -1;
}

int isEmptyChar(CharStack *s)
{
    return s->top == -1;
}
int isEmptyInt(IntStack *s)
{
    return s->top == -1;
}

void PushChar(CharStack *s, char ch)
{
    s->data[++(s->top)] = ch;
}
char PopChar(CharStack *s)
{
    return s->data[(s->top)--];
}
char TopChar(CharStack *s)
{
    return s->data[s->top];
}

void PushInt(IntStack *s, int x)
{
    s->data[++(s->top)] = x;
}
int PopInt(IntStack *s)
{
    return s->data[(s->top)--];
}

int Priority(char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0;
}

// 中缀转后缀：输出到 postfix 中
void InfixToPostfix(char *infix, char *postfix)
{
    CharStack opStack;
    InitCharStack(&opStack);
    int j = 0;
    for (int i = 0; infix[i] != '\0'; i++)
    {
        char ch = infix[i];

        if (isspace(ch))
            continue;

        if (isdigit(ch))
        {
            // 支持多位数
            while (isdigit(infix[i]))
            {
                postfix[j++] = infix[i++];
            }
            postfix[j++] = ' ';
            i--;
        }
        else if (ch == '(')
        {
            PushChar(&opStack, ch);
        }
        else if (ch == ')')
        {
            while (!isEmptyChar(&opStack) && TopChar(&opStack) != '(')
            {
                postfix[j++] = PopChar(&opStack);
                postfix[j++] = ' ';
            }
            PopChar(&opStack); // 弹出 (
        }
        else
        {
            while (!isEmptyChar(&opStack) && Priority(TopChar(&opStack)) >= Priority(ch))
            {
                postfix[j++] = PopChar(&opStack);
                postfix[j++] = ' ';
            }
            PushChar(&opStack, ch);
        }
    }

    while (!isEmptyChar(&opStack))
    {
        postfix[j++] = PopChar(&opStack);
        postfix[j++] = ' ';
    }
    postfix[j] = '\0';
}

// 计算后缀表达式
int EvaluatePostfix(char *postfix)
{
    IntStack valStack;
    InitIntStack(&valStack);

    for (int i = 0; postfix[i] != '\0'; i++)
    {
        char ch = postfix[i];

        if (isspace(ch))
            continue;

        if (isdigit(ch))
        {
            int num = 0;
            while (isdigit(postfix[i]))
            {
                num = num * 10 + (postfix[i] - '0');
                i++;
            }
            PushInt(&valStack, num);
            i--; // 回退
        }
        else
        {
            int b = PopInt(&valStack);
            int a = PopInt(&valStack);
            switch (ch)
            {
            case '+':
                PushInt(&valStack, a + b);
                break;
            case '-':
                PushInt(&valStack, a - b);
                break;
            case '*':
                PushInt(&valStack, a * b);
                break;
            case '/':
                PushInt(&valStack, a / b);
                break;
            }
        }
    }

    return PopInt(&valStack);
}

int main()
{
    char infix[MAXSIZE];
    char postfix[MAXSIZE * 2];

    printf("请输入中缀表达式（支持 + - * / 和括号）：\n");
    fgets(infix, MAXSIZE, stdin);

    InfixToPostfix(infix, postfix);

    printf("后缀表达式为: %s\n", postfix);
    int result = EvaluatePostfix(postfix);
    printf("计算结果为: %d\n", result);

    return 0;
}
